package com.base.doublepoint.listnode;

public class MiddleNode {
    /**
     * 找到链表的中间结点,如果为双数，则是最左边的结点
     */
    public ListNode middleNode(ListNode head) {
        /**
         * 单指针法，遍历两次链表
         */
        int i = 0;
        ListNode left = head;
        ListNode right = head;
        while (right != null) {
            right = right.next;
            i++;
        }
        for (int j = 1; j < i / 2 + 1; j++) {
                left=left.next;
        }
        return left;
    }

    public ListNode middleNode1(ListNode head){
        /**
         * 快慢指针
         */
        ListNode slow = head,fast =head;
        // 注意结尾条件，要求判断尾结点。如果是奇数个结点，则结尾是fast!=null&&fast.next==null;如果是偶数个结点,则结尾是fast == null
        while (fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    public static void main(String[] args) {
        ListNode node=new ListNode(0,null);
        for (int i = 1; i < 5; i++) {
            node.next=new ListNode(i,null);
        }

        MiddleNode middleNode = new MiddleNode();
        middleNode.middleNode(node);
    }
}
